COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00005 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a39.tex[106,phy] \today\hfill}

\bigskip
\line{[For Recurrences]\hfill}

\bigskip
How many ways are there to put 4  X's and 6 O's together to form a
10-character string, like:
$$\hbox{XXXXOOOOOO\qquad or\qquad OXOXXOOOOX}\;?$$
The problem is hard, so first make it easier. If there are no~X's
(and 10~O's), there is just one way:
$$\hbox{OOOOOOOOOO}\,.$$
If there is one X, there are ten ways:
$$\hbox{XOOOOOOOOO\qquad through\qquad OOOOOOOOOX}\,.$$
To place two X's, take all the ten one-X patterns and change an~O to
an~X to
each in all nine possible ways. This gives rise to ninety strings,
but each of them appears twice (both OXOOOOOOOO and OOOOXOOOOO can
be changed, by adding an~X, to
OXOOXOOOOO), so the number of different two-X patterns is
$10\cdot 9/2=45$. Similarly, the number of three-X patterns is
$45\cdot 8/3=120$, and the number of four-X patterns is $120\cdot 7/4=280$.

If $C(A,B)$ is the number of ways to place $B$ X's in $A$~places, find
the recurrence relation suggested by the previous paragraph to get
$C(A,B+1)$ from $C(A,B)$, and use it to design an algorithm, with an
iteration executed $B$~times, to compute $C(A,B)$.

\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft October 16, 1984

\bye